package com.lili.sort;

/**
 * @Auther: 李 力
 * @Date: 2024/8/2
 * @Description: 计数排序:改进
 * @version: 1.0
 */
public class CountSort2 {

    //改进:让原始数组的最小值映射到count[0] 最大值映射到count的最右侧
    public static int[] countSort2(int[] arr) {
        int maxNUm = arr[0];
        int minNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxNUm) {
                maxNUm = arr[i];
            }
            if (arr[i] < minNum) {
                minNum = arr[i];
            }
        }
        int[] count = new int[maxNUm - minNum + 1];
        //原始数组元素减去最小值为count索引
        for (int i : arr) {
            count[i - minNum]++;
        }
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                //加上最小值还原原始值
                arr[k] = i + minNum;
                count[i]--;
                k++;
            }
        }
        return arr;
    }
}
